Information markets for product attributes A game theoretic
We model the availability of information about product attributes in Internet-based markets, focusing on a phenomenon that we term as information deficit (availability of less than perfect information about product attributes) and its impact on the equilibrium strategies of sellers and buyers in electronic markets. We create a model of a market for a differentiated product and investigate how buyer uncertainty regarding the attributes of the product drives market outcomes. We show that a market for product information can partly correct the inefficiencies that arise from imperfect information and predict that product information will begin to be traded once appropriate micro-transaction payment schemes become available. We formulate a mechanism by which sellers can charge an information rent for fine-grained information about product attributes which we term as a dual pricing mechanism wherein sellers extract an information rent in addition to the price of the product from buyers. We analyze the equilibrium that results and comment on the nature of welfare gains. A key finding of the paper is that allowing sellers to charge dual rents leads to more efficient markets. This work was supported by NSF grants DMI-0121395 and SBR-9602053.
Innovating knowledge communities %2D An analysis of group collaboration and competition in science and technology.

Positioning knowledge schools of thought and new knowledge creation.

Analyzing knowledge communities using foreground and background clusters.
background clusters
Multi%2Dtask Feature Selection Using the Multiple Inclusion Criterion %28MIC%29.

Resolving Identity Uncertainty with Learned Random Walks.
A pervasive problem in large relational databases is identity uncertainty which occurs when multiple entries in a database refer to the same underlying entity in the world. Relational databases exhibit rich graphical structure and are naturally modeled as graphs whose nodes represent entities and whose typed-edges represent relations between them. We propose using random walk models for resolving identity uncertainty since they have proven effective for finding points which are proximately located in a network. Because not all types of relations are equally helpful in alleviating identity uncertainty, we develop a supervised approach to learning the usefulness of different database relations from a training set of database entries whose true identities are known. When tested on the task of resolving uncertainty of ambiguously named authors in bibliographical data, the learned random walk models yield performance superior to support vector machines, and to a related spectral clustering method.
An Approach to Web%2DScale Named%2DEntity Disambiguation.

Efficient Clustering of Web%2DDerived Data Sets.

An Approach to Web%2DScale Named%2DEntity Disambiguation.

A predictive model for identifying mini%2Dregulatory modules in the mouse genome.

Transfer Learning Using Feature Selection
6.4 Algorithms for Feature Selection using TPC.............. 37
Protein%2DProtein Interaction Network Alignment by Quantitative Simulation.
We adapt a network simulation algorithm called quantitative simulation (QSim) for use in the alignment of biological networks. Unlike most network alignment methods, QSim finds local matches for one network in another, making it asymmetric, and takes full advantage of different edge types. We use QSim to simulate a protein-protein interaction (PPI) network from D. melanogaster using a PPI network from S. cerevisiae, and compare QSim’s alignment to those from other methods using Gene Ontology (GO) biological process annotations as proxies for correct alignment matches. The best cross-species protein matches obtained from QSim have a higher agreement in GO biological process annotations than those from either BLAST or an alternative network alignment algorithm 1. 1.
Multiway Clustering for Creating Biomedical Term Sets.
We present an EM-based clustering method that can be used for constructing or augmenting ontologies such as MeSH. Our algorithm simultaneously clusters verbs and nouns using both verb-noun and noun-noun co-occurrence pairs. This strategy provides greater coverage of words than using either set of pairs alone, since not all words appear in both datasets. We demonstrate it on data extracted from Medline and evaluate the results using MeSH and Wordnet. 1.
Web%2Dscale named entity recognition.
While gazetteers can be used to perform named entity recognition through lookup-based methods, ambiguity and incomplete gazetteers lead to relatively low recall. A sequence model which uses more general features can achieve higher recall while maintaining reasonable precision, but typically requires expensive annotated training data. To circumvent the need for such training data, we bootstrap the learning of a sequence model with a gazetteer-driven labeling algorithm which only labels tokens in unlabeled data that it can label confidently. We present an algorithm, called the Partial Perceptron, for discriminatively learning the parameters of a sequence model from such partially labeled data. The algorithm is easy to implement and trains much more quickly than a state-of-the-art algorithm based on Conditional Random Fields with equivalent performance. Experimental results show that the learned model yields a substantial relative improvement in recall (77.3%) with some loss in precision (a 28.7 % relative decrease) when compared to the gazetteer-driven method.
Using sequence classification for filtering web pages.

Efficient Feature Selection in the Presence of Multiple Feature Classes.
permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the University of Pennsylvania’s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to
Regularized Learning with Networks of Features.
For many supervised learning problems, we possess prior knowledge about which features yield similar information about the target variable. In predicting the topic of a document, we might know that two words are synonyms, and when performing image recognition, we know which pixels are adjacent. Such synonymous or neighboring features are near-duplicates and should be expected to have similar weights in an accurate model. Here we present a framework for regularized learning when one has prior knowledge about which features are expected to have similar and dissimilar weights. The prior knowledge is encoded as a network whose vertices are features and whose edges represent the similarities and dissimilarities between them. During learning, each feature’s weight is penalized by the amount it differs from the average weight of its neighbors. For text classification, regularization using networks of word co-occurrences outperforms manifold learning and compares favorably to other recently proposed semi-supervised learning methods. For sentiment analysis, feature networks constructed from declarative human knowledge significantly improve prediction accuracy. 1
A model of market power and efficiency in private electronic exchanges.

Finding cohesive clusters for analyzing knowledge communities.
Documents and authors can be clustered into “knowledge communities ” based on the overlap in the papers they cite. We introduce a new clustering algorithm, Streemer, which finds cohesive foreground clusters embedded in a diffuse background, and use it to identify knowledge communities as foreground clusters of papers which share common citations. To analyze the evolution of these communities over time, we build predictive models with features based on the citation structure, the vocabulary of the papers, and the affiliations and prestige of the authors. Findings include that scientific knowledge communities tend to grow more rapidly if their publications build on diverse information and if they use a narrow vocabulary. 1.
Finding Cohesive Clusters for Analyzing Knowledge Communities.
Documents and authors can be clustered into “knowledge communities ” based on the overlap in the papers they cite. We introduce a new clustering algorithm, Streemer, which finds cohesive foreground clusters embedded in a diffuse background, and use it to identify knowledge communities as foreground clusters of papers which share common citations. To analyze the evolution of these communities over time, we build predictive models with features based on the citation structure, the vocabulary of the papers, and the affiliations and prestige of the authors. Findings include that scientific knowledge communities tend to grow more rapidly if their publications build on diverse information and if they use a narrow vocabulary. 1.
Extracting Product Comparisons from Discussion Boards.

Active learning for logistic regression an evaluation.
(will be inserted by the editor)
Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Privacy becomes a more and more serious concern in applications involving microdata. Recently, efficient anonymization has attracted much research work. Most of the previous methods use global recoding, which maps the domains of the quasi-identifier attributes to generalized or changed values. However, global recoding may not always achieve effective anonymization in terms of discernability and query answering accuracy using the anonymized data. Moreover, anonymized data is often used for analysis. As well accepted in many analytical applications, different attributes in a data set may have different utility in the analysis. The utility of attributes has not been considered in the previous methods. In this paper, we study the problem of utility-based anonymization. First, we propose a simple framework to specify utility of attributes. The framework covers both numeric and categorical data. Second, we develop two simple yet efficient heuristic local recoding methods for utility-based anonymization. Our extensive performance study using both real data sets and synthetic data sets shows that our methods outperform the state-of-the-art multidimensional global recoding methods in both discernability and query answering accuracy. Furthermore, our utility-based method can boost the quality of analysis using the anonymized data.
An Empirical Study of the Behavior of Active Learning for Word Sense Disambiguation.
This paper shows that two uncertaintybased active learning methods, combined with a maximum entropy model, work well on learning English verb senses. Data analysis on the learning process, based on both instance and feature levels, suggests that a careful treatment of feature extraction is important for the active learning to be useful for WSD. The overfitting phenomena that occurred during the active learning process are identified as classic overfitting in machine learning based on the data analysis. 1
Automatic term list generation for entity tagging.
Entity tagging is perhaps the most basic tasks in information extraction. Consequently, if any sophisticated information extraction is to be done, this task must be done well. Currently, state of the art taggers are trained with hand-labeled training data that resembles the text to which they will be applied. However, such training data is rarely abundant enough to contain more than a modest subset of entities from the target entity class. To remedy this, designers of information extraction systems frequently augment their systems with large lists of known members of the entity class so as to cover most of the prototypical, and perhaps not so prototypical, positive instances that the training data may not contain. Such entity lists, or term lists
Streamwise Feature Selection.
permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the University of Pennsylvania’s products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to
Is Online Product Information Availability Driven by Quality or Differentiation%3F

Streaming feature selection using alpha%2Dinvesting.
In Streaming Feature Selection (SFS), new features are sequentially considered for addition to a predictive model. When the space of potential features is large, SFS offers many advantages over traditional feature selection methods, which assume that all features are known in advance. Features can be generated dynamically, focusing the search for new features on promising subspaces, and overfitting can be controlled by dynamically adjusting the threshold for adding features to the model. We describe α-investing, an adaptive complexity penalty method for SFS which dynamically adjusts the threshold on the error reduction required for adding a new feature. α-investing gives false discovery ratestyle guarantees against overfitting. It differs from standard penalty methods such as AIC, BIC or RIC, which always drastically over- or under-fit in the limit of infinite numbers of non-predictive features. Empirical results show that SFS is competitive with much more compute-intensive feature selection methods such as stepwise regression, and allows feature selection on problems with over a million potential features.
CROC A New Evaluation Criterion for Recommender Systems.

Cluster%2Dbased concept invention for statistical relational learning.
We use clustering to derive new relations which augment database schema used in automatic generation of predictive features in statistical relational learning. Entities derived from clusters increase the expressivity of feature spaces by creating new first-class concepts which contribute to the creation of new features. For example, in CiteSeer, papers can be clustered based on words or citations giving &#034;topics&#034;, and authors can be clustered based on documents they coauthor giving &#034;communities&#034;. Such cluster-derived concepts become part of more complex feature expressions. Out of the large number of generated features, those which improve predictive accuracy are kept in the model, as decided by statistical feature selection criteria. We present results demonstrating improved accuracy on two tasks, venue prediction and link prediction, using CiteSeer data.
The CRASSS plug%2Din for integrating annotation data with hierarchical clustering results.

Using prior knowledge to improve genetic network reconstruction from microarray data.

Statistical Relational Learning for Document Mining.
A major obstacle to fully integrated deployment  of statistical learners is the assumption that data  sits in a single table, even though most real-world  databases have complex relational structures. In  this paper, we introduce an integrated approach  to building regression models from data stored  in relational databases. Potential features are  generated by structured search of the space of  queries to the database, and then tested for inclusion  in a logistic regression. We present experimental  results for the task of predicting where  scientific papers will be published based on relational  data taken from CiteSeer. This data includes  word counts in the document, frequently  cited authors or papers, co-citations, publication  venues of cited papers, word co-occurrences, and  word counts in cited or citing documents. Our  approach results in classification accuracies superior  to those achieved when using classical  &#034;flat&#034; features. Our classification task also serves  as a &#034;where to publish?&#034; conference/journal recommendation  task.
Dual Pricing in Electronic Markets.

Static and Dynamic Analysis of the Internet%27s Susceptibility to Faults and Attacks.
We analyze the susceptibility of the Internet to random faults, malicious attacks, and mixtures of faults and attacks. We analyze actual Internet data, as well as simulated data created with network models. The network models generalize previous research, and allow generation of graphs ranging from uniform to preferential, and from static to dynamic. We introduce new metrics for analyzing the connectivity and performance of networks which improve upon metrics used in earlier research. Previous research has shown that preferential networks like the Internet are more robust to random failures compared to uniform networks. We find that preferential networks, including the Internet, are more robust only when more than 95% of failures are random faults, and robustness is measured with average diameter. The advantage of preferential networks disappears with alternative metrics, and when a small fraction of faults are attacks. We also identify dynamic characteristics of the Internet which can be used to create improved network models. This model should allow more accurate analysis for the future Internet, for example facilitating the design of network protocols with optimal performance in the future, or predicting future attack and fault tolerance. We find that the Internet is becoming more preferential as it evolves. The average diameter has been stable or even decreasing as the number of nodes has been increasing. The Internet is becoming more robust to random failures over time, but has also become more vulnerable to attacks.
Methods and metrics for cold%2Dstart recommendations.
We have developed a method for recommending items that combines content and collaborative data under a single probabilistic framework. We benchmark our algorithm against a nave Bayes classifier on the cold-start problem, where we wish to recommend items that no one in the community has yet rated. We systematically explore three testing methodologies using a publicly available data set, and explain how these methods apply to specific real-world applications. We advocate heuristic recommenders when benchmarking to give competent baseline performance. We introduce a new performance metric, the CROC curve, and demonstrate empirically that the various components of our testing strategy combine to obtain deeper understanding of the performance characteristics of recommender systems. Though the emphasis of our testing is on cold-start recommending, our methods for recommending and evaluation are general.
Pricing price information in e%2Dcommerce.
Shopbots and Internet sites that help users locate the best price for a product are changing the way people shop by providing valuable information on goods and services. This paper presents a first attempt to measure the value of one piece of information: the price charged for goods and services. We first establish a theoretical limit to the value of price information for the first seller in a market that decides to sell price information to a shopbot and quantify the revenues that the seller can expect to receive. We then proceed to discuss whether and how much of this theoretical value can actually be realized in equilibrium settings.
An auction%2Dbased method for decentralized train scheduling.
We present a computational study of an auction-based method  for decentralized train scheduling. The method is well suited to the natural information and control structure of modern railroads. We assume separate network territories, with an autonomous dispatch agent responsible for the #ow of trains over each territory. Each train is represented by a self-interested agent that bids for the righttotravel across the network from its source to destination, submitting bids to multiple dispatch agents along its route as necessary. The bidding language allows trains to bid for the righttoenter and exit territories at particular times, and also to represent indi#erence over a range of times. Computational results on a simple network with straight-forward best-response bidding strategies demonstrate that the auction computes nearoptimal system-wide schedules. In addition, the method appears to have useful scaling properties, both with the number of trains and with the number of dispatchers, and generates less extremal solutions than those obtained using traditional centralized optimization techniques.


Rates of Convergence of Performance Gradient Estimates Using Function Approximation and Bias in Reinforcement Learning.
We address two open theoretical questions in Policy Gradient Reinforcement  Learning. The first concerns the efficacy of using function approximation  to represent the state action value function, Q. Theory is presented  showing that linear function approximation representations of Q  can degrade the rate of convergence of performance gradient estimates  by a factor of O(ML) relative to when no function approximation of Q  is used, where M is the number of possible actions and L is the number  of basis functions in the function approximation representation. The second  concerns the use of a bias term in estimating the state action value  function. Theory is presented showing that a non-zero bias term can  improve the rate of convergence of performance gradient estimates by  O(1    (1/M)), where M is the number of possible actions. Experimental  evidence is presented showing that these theoretical results lead to  significant improvement in the convergence properties of Policy Gradient  Reinforcement Learning algorithms.
Probabilistic Models for Unified Collaborative and Content%2DBased Recommendation in Sparse%2DData Environments.
Recommender systems leverage product and community information to target products to consumers. Researchers have developed collaborative recommenders, content-based recommenders, and a few hybrid systems. We propose a unified probabilistic framework for merging collaborative and content-based recommendations. We extend Hofmann’s (1999) aspect model to incorporate three-way co-occurrence data among users, items, and item content. The relative influence of collaboration data versus content data is not imposed as an exogenous parameter, but rather emerges naturally from the given data sources. However, global probabilistic models coupled with standard EM learning algorithms tend to drastically overfit in the sparsedata situations typical of recommendation applications. We show that secondary content information can often be used to overcome sparsity. Experiments on data from the ResearchIndex library of Computer Science publications show that appropriate mixture models incorporating secondary data produce significantly better quality recommenders than-nearest neighbors (-NN). Global probabilistic models also allow more general inferences than local methods like-NN. 1
Localizing Search in Reinforcement Learning.
Reinforcement learning (RL) can be impractical for many high dimensional problems because of the computational cost of doing stochastic search in large state spaces. We propose a new RL method, Boundary Localized Reinforcement Learning (BLRL), which maps RL into a mode switching problem where an agent deterministically chooses an action based on its state, and limits stochastic search to small areas around mode boundaries, drastically reducing computational cost. BLRL starts with an initial set of parameterized boundaries that partition the state space into distinct control modes. Reinforcement reward is used to update the boundary parameters using the policy gradient formulation of Sutton et al. (2000). We demonstrate that stochastic search can be limited to regions near mode boundaries, thus greatly reducing search, while still guaranteeing convergence to a locally optimal deterministic mode switching policy. Further, we give conditions under which the policy gradie...
Iterative Combinatorial Auctions Theory and Practice.
Combinatorial auctions, which allow agents to bid directly for  bundles of resources, are necessary for optimal auction-based  solutions to resource allocation problems with agents that  have non-additive values for resources, such as distributed  scheduling and task assignment problems. We introduce  iBundle, the first iterative combinatorial auction that is optimal  for a reasonable agent bidding strategy, in this case  myopic best-response bidding. Its optimality is proved with  a novel connection to primal-dual optimization theory. We  demonstrate orders of magnitude performance improvements  over the only other known optimal combinatorial auction, the  Generalized Vickrey Auction.
Clustering and Identifying Temporal Trends in Document Databases.
We introduce a simple and efficient method for clustering and identifying temporal trends in hyper-linked document databases. Our method can scale to large datasets because it exploits the underlying regularity often found in hyper-linked document databases. Because of this scalability, we can use our method to study the temporal trends of individual clusters in a statistically meaningful manner. As an example of our approach, we give a summary of the temporal trends found in a scientific literature database with thousands of documents.
Preventing Strategic Manipulation in Iterative Auctions Proxy Agents and Price%2DAdjustment.
Iterative auctions have many computational advantages over sealed-bid auctions, but can present new possibilities for strategic manipulation. We propose a two-stage technique to make iterative auctions that compute optimal allocations with myopic best-response bidding strategies more robust to manipulation. First, introduce proxy bidding agents to constrain bidding strategies to (possibly untruthful) myopic best-response. Second, after...
Clustering and Identifying Temporal Trends in Document Databases.
We introduce a simple and efficient method for clustering and identifying temporal trends in hyper-linked document databases. Our method can scale to large datasets because it exploits the underlying regularity often found in hyper-linked document databases. Because of this scalability, we can use our method to study the temporal trends of individual clusters in a statistically meaningful manner. As an example of our approach, we give a summary of the temporal trends found in a scientific literature database with thousands of documents.
Localizing Policy Gradient Estimates to Action Transition.
Function Approximation (FA) representations of the state-action value function Q have been proposed in order to reduce variance in performance gradients estimates, and thereby improve performance of Policy Gradient (PG) reinforcement learning in large continuous domains (e.g., the PIFA algorithm of Sutton et al. (in press)). We show empirically that although PIFA converges significantly faster than traditional PG algorithms such as REINFORCE which directly sample Q (without using FA), FA representations of Q are not necessary to reduce variance in performance gradient estimates, and PG algorithms which use selective direct samples of Q can converge orders of magnitude faster than PIFA. We present a new PG algorithm, called Action Transition Policy Gradient (ATPG), which uses direct samples of Q and restricts estimates of the gradient to coincide with action transitions, thus obtaining relative value estimates of executing actions, without using FA representations ...
Efficient clustering of high%2Ddimensional data sets with application to reference matching.
Many important problems involve clustering large datasets. Although naive implementations of clustering are computationally expensive, there are established efficient techniques for clustering when the dataset has either (1) a limited number of clusters, (2) a low feature dimensionality, or (3) a small number of data points. However, there has been much less work on methods of efficiently clustering datasets that are large in all three ways at once, for example, having millions of data points that exist in many thousands of dimensions representing many thousands of clusters. We present a new technique for clustering these large, high-dimensional datasets. The key idea involves using a cheap, approximate distance measure to efficiently divide the data into overlapping subsets we call canopies. Then clustering is performed by measuring exact distances only between points that occur in a common canopy. Using canopies, large clustering problems that were formerly impossible become practical. Under reasonable assumptions about the cheap distance metric, this reduction in computational cost comes without any loss in clustering accuracy. Canopies can be applied to many domains and used with a variety of clustering approaches, including Greedy Agglomerative Clustering, K-means and Expectation-Maximization. We present experimental results on grouping bibliographic citations from the reference sections of research papers. Here the canopy approach reduces computation time over a traditional clustering approach by more than an order of magnitude and decreases error in comparison to a previously used algorithm by 25%.
Accounting for Cognitive Costs in On%2DLine Auction Design.
Many auction mechanisms, including first and second price  ascending and sealed bid auctions, have been proposed and analyzed in  the economics literature. We compare the usefulness of different mechanisms  for on-line auctions, focusing on the cognitive costs placed on users  (e.g. the cost of determining the value of a good), the possibilities for  agent mediation, and the trust properties of the auction. Different auction  formats prove to be attractive for agent mediated on-line auctions  than for traditional off-line auctions. For example, second price sealed  bid auctions are attractive in traditional auctions because they avoid  the communication cost of multiple bids in first price ascending auctions,  and the &#034;gaming&#034; required to estimate the second highest bid in  first price sealed bid auctions. However, when bidding agents are cheap,  communication costs cease to be important, and a progressive auction  mechanism is preferred over a closed bid auction mechanism, since users  with semi-autonomous agents can avoid the cognitive cost of placing an  accurate value on a good. As another example, when an on-line auction  is being conducted by an untrusted auctioneer (e.g. the auctioneer is selling  its own items), rational participants will build bidding agents that  transform second price auctions into first price auctions.
Characterizing the generalization performance of model selection strategies.
: We investigate the structure of model selection problems via the bias/variance decomposition. In particular, we characterize the essential structure of a model selection task by the bias and variance profiles it generates over the sequence of hypothesis classes. This leads to a new understanding of complexity-penalization methods: First, the penalty terms in effect postulate a particular profile for the variances as a function of model complexity--- if the postulated and true profiles do not match, then systematic under-fitting or over-fitting results, depending on whether the penalty terms are too large or too small. Second, it is usually best to penalize according to the true variances of the task, and therefore no fixed penalization strategy is optimal across all problems. We then use this bias/variance characterization to identify the notion of easy and hard model selection problems. In particular, we show that if the variance profile grows too rapidly in relation to the biases t...
Active Learning for Vision%2DBased Robot Grasping.

Active Exploration and Learning in real%2DValued Spaces using Multi%2DArmed Bandit Allocation Indices.

Automatic Rebuilding of Qualitative Models for Diagnosis.

